#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>

using namespace std;

//int main()
//{
//	int arr[] = { 3, 5, 2, 1, 15, 11 };
//	unordered_set<int> us;
//	for (int e : arr)
//		us.insert(e);
//
//	unordered_set<int>::iterator it = us.begin();
//	while (it != us.end())
//	{
//		cout << *it << endl;
//		++it;
//	}
//	cout << endl;
//
//	unordered_map<string, string> dict;
//	dict.insert(make_pair("hello", "你好"));
//	dict["apple"] = "苹果";
//	dict["left"];
//
//	for (auto& kv : dict)
//	{
//		cout << kv.first << " : " << kv.second << endl;
//	}
//
//	return 0;
//}

//int main()
//{
//	const size_t N = 10000000;
//
//	unordered_set<int> us;
//	set<int> s;
//
//	vector<int> v;
//	v.reserve(N);
//	srand(time(0));
//	for (size_t i = 0; i < N; ++i)
//	{
//		//v.push_back(rand());
//		//v.push_back(rand()+i);
//		v.push_back(i);
//	}
//
//	size_t begin1 = clock();
//	for (auto e : v)
//	{
//		s.insert(e);
//	}
//	size_t end1 = clock();
//	cout << "set insert:" << end1 - begin1 << endl;
//
//	size_t begin2 = clock();
//	for (auto e : v)
//	{
//		us.insert(e);
//	}
//	size_t end2 = clock();
//	cout << "unordered_set insert:" << end2 - begin2 << endl;
//
//
//	size_t begin3 = clock();
//	for (auto e : v)
//	{
//		s.find(e);
//	}
//	size_t end3 = clock();
//	cout << "set find:" << end3 - begin3 << endl;
//
//	size_t begin4 = clock();
//	for (auto e : v)
//	{
//		us.find(e);
//	}
//	size_t end4 = clock();
//	cout << "unordered_set find:" << end4 - begin4 << endl << endl;
//
//	cout <<"插入数据个数："<< s.size() << endl;
//	cout <<"插入数据个数：" << us.size() << endl << endl;;
//
//	size_t begin5 = clock();
//	for (auto e : v)
//	{
//		s.erase(e);
//	}
//	size_t end5 = clock();
//	cout << "set erase:" << end5 - begin5 << endl;
//
//	size_t begin6 = clock();
//	for (auto e : v)
//	{
//		us.erase(e);
//	}
//	size_t end6 = clock();
//	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
//	
//	return 0;
//}

//#include "HashTable.h"

//int main()
//{
//	HashTable<int, int> ht;
//	int a[] = { 1,111,4,7,15,25,44,9 };
//	for (auto e : a)
//	{
//		ht.insert(make_pair(e, e));
//	}
//
//	ht.erase(4);
//
//
//	return 0;
//}

//int main()
//{
//	//HashTable<string, string> dict;
//	//
//	//dict.insert(make_pair("hello", "你好"));
//
//	//defaultHashFunc<string> hf;
//
//	//cout << hf("abcd") << endl;
//	//cout << hf("bcda") << endl;
//	//cout << hf("aade") << endl;
//
//
//	return 0;
//}
//

//int main()
//{
//    hash_bucket::HashTable<int, int> ht;
//    int a[] = { 1,111,4,7,15,25,44,9,14};
//    for (auto e : a)
//    {
//        ht.insert(make_pair(e, e));
//    }
//    
//    ht.Print();
//
//    ht.erase(14);
//    ht.erase(44);
//    ht.erase(4);
//    ht.Print();
//
//    hash_bucket::HashTable<string, string> dict;
//    dict.insert(make_pair("hello", "你好"));
//    dict.insert(make_pair("world", "世界"));
//    dict.insert(make_pair("right", "右边"));
//    dict.insert(make_pair("left", "左边"));
//    dict.Print();
//
//    hash_bucket::HashTable<string, string> dictCopy(dict);
//    dictCopy.Print();
//    return 0;
//}

#/*include "UnorderedMap.h"
#include "UnorderedSet.h"

int main()
{
	xyx::Unordered_Map<string, string> dict;
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("right", "右边"));

	xyx::Unordered_Set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(1);
	s.insert(3);

	xyx::Unordered_Set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	
	dict["insert"] = "插入";
	dict["apple"] = "苹果";
	dict["car"];

	for (auto& kv : dict)
	{
		cout << kv.first << " ; " << kv.second << endl;
	}
	cout << endl;

	return 0;
}*/

#include "BitSet.h"

//int main()
//{
//	//xyx::BitSet<1000> bs;
//	//bs.set(1);
//	//bs.set(10);
//	//bs.set(100);
//
//	//cout << bs.check(1) << endl;
//	//cout << bs.check(10) << endl;
//	//cout << bs.check(100) << endl;
//	//cout << bs.check(999) << endl << endl;
//
//	//bs.reset(100);
//	//bs.set(999);
//
//	//cout << bs.check(1) << endl;
//	//cout << bs.check(10) << endl;
//	//cout << bs.check(100) << endl;
//	//cout << bs.check(999) << endl << endl;
//
//	int a = 1;
//
//	return 0;
//}

#include"BloomFilter.h"

//int main()
//{
//	int arr[] = { 1,2,3,3,3,2,1,5,6,5,7,9,8,8 };
//
//	tbitset<10> tbs;
//
//	for (int e : arr)
//		tbs.Set(e);
//
//	for (int e : arr)
//	{
//		if (tbs.Test(e))
//			cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}
//

//int main()
//{
//	BloomFilter<100, string> bf;
//	bf.Set("孙悟空");
//	bf.Set("唐三藏");
//	bf.Set("猪八戒");
//
//	cout << bf.Test("孙悟空") << endl;
//	cout << bf.Test("唐三藏") << endl;
//	cout << bf.Test("猪八戒") << endl;
//	cout << bf.Test("沙僧") << endl;
//	return 0;
//}

void TestBloomFilter2()
{
	srand(time(0));
	const size_t N = 100000;
	BloomFilter<N ,string> bf;

	std::vector<std::string> v1;
	std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是总体不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "csdn.com";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

int main()
{
	TestBloomFilter2();
	return 0;
}